home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / C / CHAMBERS.ZIP / CHAMBERS.TXT
Encoding:
Text File  |  1996-02-19  |  14.8 KB  |  420 lines
  1.     "A cryptographic pseudorandom number generator"
  2.  
  3.             by Bill Chambers
  4.  
  5. /* Feb 28, 95:
  6. DESCRIPTION: This is a 32-bit pseudorandom sequence generator, which is keyed
  7. by a character string. It is designed for machines with 32-bit (unsigned) long
  8. ints, and 8-bit (unsigned) chars. 
  9.  
  10. USAGE: for normal use compile with RUN_TEST set to 0 and with REKEY set to 1.
  11. Initialise by 'void set_yy32(char *key, int keylen)'. The key can be up to 1536
  12. bytes long, but up to 256 is recommended. Then one can delete the key for
  13. security, as the internal tables are now set; then repeatedly use 'unsigned
  14. long int yy32(void)'. Finally for security call set_yy32(char *key, int keylen)
  15. again with a dummy key, followed by yy32(); this will reset the tables. 
  16.  
  17. APPLICATION: For situations where a key-stream can be used. Usually this is
  18. XOR'd bit-by-bit with the plaintext. Stream-ciphers should be faster and
  19. stronger than block ciphers, but are not always suitable. Moreover certain
  20. precautions have to be taken, such as never re-using the same key. (This is a
  21. problem shared with the one-time-pad system.) Also "random access" to the
  22. key-stream is impractical, so that decryption has to be from the beginning of
  23. the text. 
  24.  
  25. PURPOSE AND BACKGROUND: This program combines two types of stream-cipher
  26. algorithm, and hopefully keeps the advantages of each. The slower algorithm is
  27. used to rekey the faster one every eight steps, to foil cryptanalytic methods
  28. that require a large amount of output for each key-value. The fast algorithm
  29. (in yy32) is a Jenkins generator, as proposed by Bob Jenkins, 765 San Antonio
  30. #69, Palo Alto, CA 94303 (rjenkins@us.oracle.com). This is a table-modifier,
  31. which should be cryptographically very strong, although there is not much
  32. theory behind it. It has resemblances to 'alleged-RC4', and was designed so
  33. that even when scaled down it gave good results in statistical tests. The
  34. cascade-generator (in cascade8_yy) has a known period ((2**32-1)**8), just less
  35. than 2**256, and it is also known that the frequency distribution of the
  36. output-values over a period is maximally flat. (For the theory see 'Fast
  37. Software Encryption', Ross Anderson (Ed.), Lecture Notes in Computer Science
  38. 809 (1994), 51-55 (W G Chambers). The generator is closely related to the
  39. Gollmann clock-controlled cascades.) On the other hand it is about five times
  40. as slow as the Jenkins generator, and the code for initialising its tables is
  41. moderately lengthy. The rekeying system enables one to have a fairly fast
  42. algorithm with an almost certain guarantee on a lower bound for the period. 
  43.  
  44. STRUCTURE: There are three important procedures. The first one is a
  45. key-expansion routine 'keyexpand_yy()', only used in the initial phase, to set
  46. the lookup tables of the second procedure, 'cascade8_yy()', a
  47. 'cascade'-generator. This procedure is not only used to set up the tables of
  48. the third procedure 'yy32()', a Jenkins generator, but it is also used in
  49. effect to rekey it, feeding in one pseudo-random value for every eight outputs.
  50.  
  51. Externally available routines are void set_yy32(char *key, int keylen) and
  52. unsigned long yy32(void), which returns a 32-bit string. Internal routines are
  53. keyexpand_yy() and cascade8_yy(). 
  54.  
  55. FLAGS: There are three flags for controlling the compilation. If REKEY is set
  56. non-zero, then the operation is as described. If REKEY is set to 0, then the
  57. programme operates as a Jenkins generator, with the cascade-generator only used
  58. for initialisation. This is for carrying out time-trials. If RUN_TEST is set
  59. non-zero, then the programme runs a test of a million cycles. If RUN_TEST is
  60. set to 0, then the programme acts as a subroutine for generating random
  61. numbers, plus a key-setting subroutine. There is also a third flag, TEST_JBOX,
  62. which determines whether the Jbox[] look-up table is checked for certain
  63. mathematical properties needed to guarantee the period. 
  64.  
  65. TABLES: The following tables are used:
  66. A) unsigned char Sbox[256] in keyexpand_yy(); this is unset when the procedure
  67. is decommissioned by the set-up part of cascade8_yy().
  68. B) unsigned long Sbox[256], Jbox[256] in cascade8_yy(); these have to have
  69. special properties to guarantee the period. 
  70. C) Mtab[256] and Optab[256] in yy32(); the first table is modified slightly on
  71. each iteration, and the second is simply for buffering the output, and is
  72. strictly not necessary. It could be used to hold the text to be processed. 
  73.  
  74. RESEARCH QUESTION: In a rekeyed system, how should the resources, both of
  75. time and memory, be shared between the driving and the driven generators?
  76.  
  77.  
  78. WARNING!! For 32-bit machines only!! Also at the places marked 1s-COMP it
  79. is assumed that if an unsigned long is decreased by the addition of another
  80. unsigned long, then overflow has occurred. **/
  81.  
  82.  
  83.  
  84. /******************* MAIN ***********************/
  85.  
  86. #define REKEY 1 /** if set to 0, program runs as a pure Jenkins generator **/
  87. #define RUN_TEST 1 /** 0 if you want a random-number generator **/
  88.  
  89. #define JBOX_TEST 1 /** 0 if you don't want to test the J-boxes **/
  90. #define UINT32 unsigned long int
  91.  
  92. #include <stdio.h>
  93. #include <stdlib.h>
  94.  
  95. #if RUN_TEST
  96. main() {
  97. #include <string.h>
  98. #include <time.h>
  99.  
  100. UINT32 val, yy32();
  101. long int j, ta;
  102. char key[256];
  103. int keylen, teston, ptr;
  104. void set_yy32();
  105.  
  106. static unsigned long test[] =
  107. #if REKEY
  108. {0xf11eef42, 0xe66d2c0e, 0x3cd0ce84, 0x13fa419f, 0x952f6a73, 0x67618a2a,
  109. 0x79020459, 0xc2a5abe4, 0x7584d1c9, 0x6a096097, 0x8df4feb0, 0xf9845e1d,
  110. 0xb913e735, 0x4ee1638c, 0xf8bd6898};
  111. #else
  112. {0x8ac50488, 0xe287225b, 0xa5336781, 0x30c18c59, 0x6a408ec3, 0x15e7b6ad,
  113. 0xfe6a88a7, 0xe9d2d50d, 0x3f772ed7, 0xa870f689, 0xd0669fa0, 0x6c4da4e6,
  114. 0x25be0b0e, 0xcdabd69, 0x47533b2};
  115. #endif
  116.  
  117. printf("key? (0 for test): ");
  118. scanf("%255s", key);
  119. if(strcmp(key, "0") == 0) strcpy(key, "qwertyuiop");
  120.  
  121. keylen = strlen(key);
  122. printf("key = %s, keylen = %d\n", key, keylen);
  123. teston = (strcmp(key, "qwertyuiop") == 0);
  124. if(teston) printf("testing op\n");
  125.  
  126. ptr = 0;
  127. ta = clock();
  128. set_yy32(key, keylen);
  129. printf("delta-t = %d\n", clock() - ta);
  130. ta = clock();
  131. for(j=0; j<1000000; j++)
  132.   {val = yy32();
  133.    if(((j+1) & (0200000 - 1)) == 0)
  134.      {printf("%10lx", val);
  135.       if(teston && (test[ptr++] != val))
  136.          printf("  DISAGREEMENT WITH TEST RESULTS\n");
  137.        else
  138.          printf("\n");
  139.       }
  140.    }
  141. printf("delta-t = %d\n", clock() - ta);
  142. }
  143. #endif /** RUN-TEST **/
  144.  
  145. /*********** GLOBAL VARIABLES ***********/
  146. static int Keyexpand_READY = 0, Cascade8_READY = 0, Yy32_READY = 0;
  147. static char *Key = NULL;
  148. static int  Keylen = 0;
  149. static int Op_ptr = -1; /** declare yy32() has empty op-buffer table **/
  150.  
  151. /************* KEYEXPAND_YY **************************/
  152.  
  153. /** this is a byte-oriented key-expander using an invertible s-box
  154. with three cornered swapping, similar to alleged-RC4 **/ 
  155.  
  156. static UINT32 keyexpand_yy(burn_flag)
  157. int burn_flag;
  158. {
  159. UINT32 ans;
  160. static unsigned char Sbox[256], Xx, Yy, Count;
  161. unsigned char c, a, b;
  162. int cc, i, keyptr, keylenp;
  163.  
  164. /** Note that when this routine is called for the first time, it initialises
  165. itself before proceeding with the main business **/
  166.  
  167. if(burn_flag != 0)  /** BURN tables **/
  168.   {Xx = Yy = 0; 
  169.    for(i=0; i<256; i++)
  170.       Sbox[i] = 0;
  171.    Keyexpand_READY = 0;
  172.    Key = NULL; Keylen = 0;
  173.    return 0L;}
  174.  
  175. if(!Keyexpand_READY)
  176.   {if((Key == NULL) || (Keylen <= 0))
  177.      {fprintf(stderr, " No Key set\n"); exit(1);}
  178.    keylenp = Keylen + (01 ^ (Keylen & 01)); /** make it odd! **/
  179.    keyptr=0;
  180.  
  181.    Xx = 1; Yy = 2; 
  182.    for(i=0; i<256; i++)
  183.       Sbox[i] = i;
  184.  
  185.    for(cc=0; cc<6; cc++) /** do it six times for a real stir **/
  186.       for(i=0; i<256; i++)
  187.         {Xx ^= (keyptr < Keylen? Key[keyptr]: Keylen & 0377);
  188.          if(++keyptr >= keylenp) keyptr = 0;
  189.          Yy = Sbox[((Yy^(i+cc)) + Sbox[Xx]) & 0377];
  190.          Xx = Sbox[Xx ^ Sbox[Yy]];         
  191.          c = Sbox[i]; /* gives a perm even if (Xx==i) || (Yy==i) || (Xx==Yy) */
  192.          Sbox[i] = Sbox[Xx];
  193.          Sbox[Xx] = Sbox[Yy];
  194.          Sbox[Yy] = c;
  195.          }
  196.    Count = 0;
  197.    Keyexpand_READY=1;
  198.    }
  199.  
  200. for(ans=0, cc=0; cc<4; cc++)
  201.   {Yy = Sbox[((Yy^Count) + Sbox[Xx]) & 0377];
  202.    Xx = Sbox[Xx ^ Sbox[Yy]];         
  203.    c = Sbox[Count];
  204.    a = Sbox[Count] = Sbox[Xx];
  205.    b = Sbox[Xx] = Sbox[Yy];
  206.    Sbox[Yy] = c;
  207.    Count = (Count + 1) & 0377;
  208.    ans = (ans << 8) ^ Sbox[((c^a) + b) & 0377];
  209.    }
  210. return ans;
  211. }
  212.  
  213. /*********** CASCADE8_YY *****************/
  214.  
  215. /** See 'Fast Software Encryption', Ross Anderson (Ed.),
  216. LNCS 809 (1994), 51-55 (W G Chambers) and 127-134 (David Wheeler) **/
  217.  
  218. /* Routine is FIRST called by set_yy32() to set up tables and then
  219. decommission keyexpand_yy() */
  220.  
  221. static UINT32 cascade8_yy()
  222. {
  223. #define BPW32 32 /** assumed to be number of bits in a word **/
  224. #define NREGS 8 /* the length of the cascade */
  225. #define NREGSM1 (NREGS-1)
  226. #define L2SBS 8 /** log of sbox size **/
  227. #define L2JBS 8 /** log of jump-box size **/
  228. #define JBS (01L << L2JBS)
  229. #define MASKJB (JBS -1) /* for masking bits to select jump */
  230.  
  231. long int j, nbits, k, count, pp, ptr;
  232. UINT32 keyexpand_yy(), old_r, r, op, inval, p_sum[5], t0,t1, temp, sum;
  233. static UINT32
  234.    RegB, Reg[NREGSM1], /* counters mod 2^32-1 */
  235.    StepB, Jbox[JBS], /* jump table */
  236.    Sbox[01L << L2SBS]; /* specially organised s-boxes */
  237.  
  238. static UINT32 Pf[5] = {3, 5, 0x11, 0x101, 0x10001}; /* prime factors of 2^32-1 */
  239. /* 2^32-1 divided by its five prime factors in turn */
  240. static UINT32 Nn[5] = {0x55555555, 0x33333333, 0xf0f0f0f, 0xff00ff, 0xffff};
  241.  
  242. /** Note that when this routine is called for the first time, it initialises
  243. itself with several calls to keyexpand_yy(), which is finally decomissioned.
  244. The output is a dummy value **/
  245.  
  246. if(Cascade8_READY) /** Here is the part executed every time except the FIRST **/
  247.   {old_r = RegB;
  248.    if((r = old_r + StepB) < old_r) r++; /* 1s-COMP */
  249.    op = RegB = r;
  250.    op = (op >> L2SBS) ^ Sbox[op & ((01L<<L2SBS)-1)];
  251.  
  252.    for(count=NREGSM1; count--; ) /* in effect count drops from NREGSM1-1 to 0 */
  253.      {old_r = Reg[count];
  254.       if((r = old_r + Jbox[op & MASKJB]) < old_r) r++; /* 1s-COMP */
  255.       op += (Reg[count] = r);
  256.       op = (op >> L2SBS) ^ Sbox[op & ((01L<<L2SBS)-1)];
  257.       }
  258.    return op;
  259.    }
  260.         /** INITIALISE: set registers to non-zero values **/
  261. if((RegB = keyexpand_yy(0)) == 0)
  262.    RegB = 1;
  263. for(j=NREGSM1; j--; ) /* in effect j drops from NREGSM1-1 to 0 */
  264.    if((Reg[j] = keyexpand_yy(0)) == 0)
  265.       Reg[j] = (NREGSM1 + 1) - j;
  266.  
  267.     /** set up Jbox, last two entries done later. Each entry is rel prime
  268.     to 2^32 -1, with the sum of all entries zero mod 2^32 - 1. **/
  269. for(ptr=0; ptr<JBS; ptr++)
  270.   {inval = keyexpand_yy(0);
  271.    for(old_r=0, pp=0; pp<5; pp++)
  272.      {nbits = 01 << pp;
  273.       temp = (1 + (inval & ((01L << nbits) - 1)));
  274.       inval >>= nbits;
  275.       if((r = old_r + temp*Nn[pp]) < old_r) r++; old_r = r; /* 1s-COMP */
  276.       }
  277.    Jbox[ptr] = old_r;
  278.    }
  279. StepB = Jbox[JBS-1]; /** last entry transferred to StepB **/
  280.     /** prepare last two entries so that sum is multiple of 2**32-1 **/
  281. for(sum=0, ptr=0; ptr<JBS-1; ptr++)
  282.   {if((r = sum + Jbox[ptr]) < sum) r++; sum = r;} /* 1s-COMP */
  283. t0 = Jbox[JBS-2]; t1 = 0xffffffff - sum; /** negative mod 2**32-1 **/
  284. for(pp=0; pp<5; pp++)
  285.    if(t1%Pf[pp] == 0)
  286.      {if((r = t0 - Nn[pp]) > t0) r--; t0 = r; /* 1s-COMP, drop t0 */
  287.       if((r = t1 + Nn[pp]) < t1) r++; t1 = r; /* 1s-COMP, raise t1 */
  288.       if((t0%Pf[pp]) == 0) /* do it again */
  289.         {if((r = t0 - Nn[pp]) > t0) r--; t0 = r;  /* 1s-COMP, drop t0 */
  290.          if((r = t1 + Nn[pp]) < t1) r++; t1 = r;} /* 1s-COMP, raise t1 */
  291.       }
  292. Jbox[JBS-2] = t0; Jbox[JBS-1] = t1;
  293.  
  294. #if JBOX_TEST    /** test your Jbox **/
  295. for(pp=0; pp<5; pp++)
  296.    p_sum[pp] = 0;
  297. for(ptr=0; ptr<JBS; ptr++)
  298.   {for(pp=0; pp<5; pp++)
  299.      {p_sum[pp] += (op = Jbox[ptr] % Pf[pp]);
  300.       if(op == 0)
  301.         {fprintf(stderr, "CRASH on Jbox setup!!\n"); exit(1);}
  302.       if(((ptr+1) & 0377) == 0)
  303.          p_sum[pp] %= Pf[pp]; /* overflow prevention */
  304.       }
  305.    }
  306. for(pp=0; pp<5; pp++)
  307.    if((p_sum[pp] % Pf[pp]) != 0)
  308.      {fprintf(stderr, "sum-test CRASH on Jbox setup!!\n"); exit(1);};
  309. for(pp=0; pp<5; pp++)
  310.    if((StepB % Pf[pp]) == 0)
  311.      {fprintf(stderr, "CRASH on StepB setup!!\n"); exit(1);}
  312. #endif /** JBOX_TEST **/
  313.         /** set up special s-boxes **/
  314. /** the top L2SBS bits are a perm of the address, and the rest are random. Thus
  315. when later the op is processed by 
  316.    op = (op >> L2SBS) ^ Sbox[op & ((01L<<L2SBS)-1)]
  317. we have a reversible mapping and a r-circ shift. The r-shift MUST be logical,
  318. with zero-fill on the left, so 'op' must be unsigned long.
  319. See Lecture Notes in Computer Science 809 (1994),127-134 (David Wheeler). **/ 
  320.  
  321. for(k=(01L<<L2SBS)-1; k>=0; k--) /* set up the permutation */
  322.    Sbox[k] = k;
  323. for(k=(01L<<L2SBS)-1; k>=0; k--)
  324.   {j = keyexpand_yy(0)%(k+1);
  325.    r = Sbox[k];
  326.    Sbox[k] = Sbox[j];
  327.    Sbox[j] = r;
  328.    }
  329. for(k=(01L<<L2SBS)-1; k>=0; k--)
  330.    Sbox[k] = (Sbox[k] << (BPW32-L2SBS))
  331.       ^ (keyexpand_yy(0) & ((01L<<(BPW32-L2SBS))-1));
  332.  
  333. keyexpand_yy(-1); /** force BURN of keyexpand's tables **/
  334. Cascade8_READY = 1;
  335. return 0L;
  336. }
  337.  
  338. /************* SET_YY32 *****************/
  339.  
  340. void set_yy32(key, keylen)
  341. char *key;
  342. int keylen;
  343. {
  344. UINT32 cascade8_yy();
  345.  
  346. Key = key; Keylen = keylen; /** put as global variables, and unset all flags **/
  347. Keyexpand_READY = Cascade8_READY = Yy32_READY = 0;
  348. Op_ptr = -1;
  349.  
  350. cascade8_yy(); /* dummy FIRST call to set tables and decomission keyexpand_yy */
  351. }
  352.  
  353. /************* YY32 *********************/
  354.  
  355. /** use modified PRNG suggested by Bob Jenkins, 765 San Antonio
  356. #69, Palo Alto, CA 94303 (rjenkins@us.oracle.com), but with odd changes **/ 
  357.  
  358. UINT32 yy32()
  359. {
  360. #define BPW32 32 /** assumed to be number of bits in a word **/
  361. #define L2MTS 8 /** log of mtab size **/
  362. #define MTS (01 << L2MTS) /** type 'int' **/
  363. #define MASKMT (MTS -1) /* for masking adress of mtab[] */
  364.  
  365. static UINT32 Optab[MTS], Mtab[MTS], A, B;
  366. register UINT32 inject, x, y, a, b;
  367. register int ptr;
  368. UINT32 cascade8_yy();
  369.  
  370. /** Note that when this routine is called for the first time, it initialises
  371. itself with several calls to cascade8_yy(), which is also called once in
  372. every eight iterations to provide 'rekeying' **/ 
  373.  
  374. if(Op_ptr >= 0) /** set by set_yy32() **/
  375.    return Optab[Op_ptr--];
  376.  
  377. if(!Yy32_READY)
  378.   {B = cascade8_yy();
  379.    A = cascade8_yy();
  380.    for(ptr=MTS; ptr--; ) /* ptr effectively drops from MTS-1 to 0 */
  381.       Mtab[ptr] = cascade8_yy();
  382.    Yy32_READY = 1;
  383.    }
  384.  
  385. #if REKEY
  386. a = A; b = B; /** take out of static storage **/
  387. for(ptr=MTS; ; )
  388.   {if((ptr-- & 07) == 0) /** decrement ptr here! **/
  389.      {if(ptr >= 0)  /** strange loop-exit to cut down on 'if's **/
  390.          inject = cascade8_yy();
  391.        else
  392.          break;
  393.       }
  394.    a = ((a << 19) ^ (a >> (BPW32-19))) + Mtab[ptr ^ (MTS/2)];
  395.    x = Mtab[ptr];
  396.    y = (a+b) ^ Mtab[x & MASKMT];
  397.    Mtab[ptr] = inject ^ y;
  398.    Optab[ptr] = b = x + Mtab[y >> (BPW32 - L2MTS)];
  399.    }
  400. A = a; B = b;
  401.  
  402. #else /** NOT REKEY **/
  403. a = A; b = B; /** take out of static storage **/
  404. for(ptr=MTS-1; ptr>=0; ptr--)
  405.   {a = ((a << 19) ^ (a >> (BPW32-19))) + Mtab[ptr ^ (MTS/2)];
  406.    x = Mtab[ptr];
  407.    y = (a+b) ^ Mtab[x & MASKMT];
  408.    Mtab[ptr] = y;
  409.    Optab[ptr] = b = x + Mtab[y >> (BPW32 - L2MTS)];
  410.    }
  411. A = a; B = b;
  412. #endif /** REKEY **/
  413.  
  414. Op_ptr = MTS-1;
  415. return Optab[Op_ptr--];
  416. }
  417.  
  418.  
  419.  
  420.